#include <iostream>
using namespace std;
#include <time.h>
#include <stdlib.h>
int comp(const void* a, const void* b) {
 	return *(int *)a - *(int *)b;
}
void printData(int* data, int n) {
	for (int i = 0; i < n; i++) {
		int tmp = i % 5;
		cout << data[i] << "\t";
		if (tmp == 4) cout << endl;
	}
}
int getData(int* data, int n) {
	srand((unsigned) time(NULL));
	for (int i = 0; i < n; i++){
		data[i] = rand()% 100;
	}
	qsort(data,n,sizeof(int),comp);
	printData(data, n);
	return rand()% 100;
}

int binarySearch(int* data, int n, int num) {
	int start, end;
	for (start = 0, end = n; start < end;) {
		int index = (start + end) / 2;
		if (data[index] == num) {
			return index;
		} else {
			if (data[index] > num) {
				end = index;
			} else {
				start = index;
			}
		}
	}
	return -1;
}

int binarySearchIndex(int* data, int n) {
	int start, end;
	for (start = 0, end = n; start < end;) {
		int index = (start + end) / 2;
		if (data[index] == index) {
			return index;
		} else {
			if (data[index] > index) {
				end = index;
			} else {
				start = index;
			}
		}
	}
	return -1;
}

int main() {
	int data[100];
	int random = getData(data, 100);
	int position1 = binarySearch(data, 100, data[random]);
	int position2 = binarySearchIndex(data, 100);
	cout << "data[random] : \t" << data[random] << "\tposition1 : " << position1 << endl;
	cout << "position : \t" << position2 << " \tdata[position] : " << data[position2] << endl;
	return 0;
}

